package org.example.myleet.p575;

public class Solution {
    /**
     * 思路：归纳
     * 妹妹拿到的糖果种类数目最多可以是所有糖果种类数目，但不能超过糖果数量的一半
     * 由于题目数字范围包含-100000，需要转成正数才可以用于数组下标做索引
     */
    public int distributeCandies(int[] candyType) {
        int n = candyType.length;
        int half = n / 2;
        int size = 0;
        int base = 100000;
        boolean[] map = new boolean[2 * base + 2];
        for (int candy : candyType) {
            //求得糖果种类的索引
            int t = candy + base;
            if (!map[t]) {
                //统计糖果种类数目
                map[t] = true;
                ++size;
            }
            if (size == half) {
                //不能超过糖果数量的一半
                return size;
            }
        }
        return size;
    }
}
